package com.duoduo.剑指Offer;

import com.duoduo.Node;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: algorithm
 * @description: 复杂链表的复制05
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 *
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 *
 * @author: chaidl  ！
 * @create: 2022-05-22 00:10
 */
class 复杂链表的复制05 {
	public Node copyRandomList(Node head) {
		if (head == null) {
		    return null;
		}
		Node curr=head;
		//1. 复制各节点，并构建拼接链表
		//构建   A->A`-B->B`->C->C`
		while (curr!=null){
			Node newNode =new Node(curr.val);
			newNode.next=curr.next;
			curr.next=newNode;
			curr=newNode.next;
		}
		// 2. 构建各新节点的 random 指向
		curr=head;
		while (curr != null) {
			//在这里是因为构建的节点链表是 A->A`-B->B`->C->C`，所以curr.next.random = curr.random.next;
		    if (curr.random!=null){
			    curr.next.random = curr.random.next;
		    }
			curr=curr.next.next;
		}
		// 3. 拆分两链表
		curr=head.next;
		Node prev=head,res=head.next;
		while (curr.next!=null){
			//A->B
			prev.next=prev.next.next;
			//A`->B`
			curr.next=curr.next.next;
			prev=prev.next;
			curr=curr.next;
		}
		prev.next=null;
		return res;
	}
	// 将原链表遍历每一个元素，key为node,value还是node，相当于把链表移动到map的value里面了
	Map<Node, Node> cachedNode = new HashMap<Node, Node>();
	public Node copyRandomLis2t(Node head) {
		// 首先要判断边界，基本上每一个算法题都要判断边界问题
		if (head == null) {
			return null;
		}
		Node curr=head;
		// 第一次遍历，把就得链表复制到新的链表中，这是新的map中链表是没有连接关系的
		while(curr!=null){
			Node newCachNode=new Node(curr.val);
			cachedNode.put(curr,newCachNode);
			curr=curr.next;
		}
		// 第二次遍历,分别处理新缓存中下一个指针和随即指针
		curr=head;
		while(curr!=null){
			// 从新链表拿到值
			Node  newCurr=cachedNode.get(curr);
			//获取元数据的下一个指针
			Node oldNext=curr.next;
			// 从map中获取下一个元素的数据
			Node newNext=cachedNode.get(oldNext);
			// 赋值给按当前元素的next指针
			newCurr.next=newNext;
			// 获取当前指针随机指针
			Node oldRandom=curr.random;
			Node newRandom=cachedNode.get(oldRandom);
			newCurr.random=newRandom;
			curr=curr.next;
		}
		return cachedNode.get(head);
	}
}
